//
// Created by 紫霄 on 2020/4/20.
//

#ifndef LEETCODE_42_H
#define LEETCODE_42_H
#include <vector>
using namespace std;

class Solution {
public:
  int maxSubArray(vector<int> &nums) {
    int ans = nums[0];
    vector<int> curMax;
    curMax.push_back(nums[0]);
    if (nums.size() == 1) {
      return nums[0];
    }
    for (int i = 1; i < nums.size(); ++i) {
      if (curMax[i - 1] < 0) {
        curMax.push_back(nums[i]);
        if (nums[i] > ans) {
          ans = nums[i];
        }
      } else {
        curMax.push_back(curMax[i - 1] + nums[i]);
        if (curMax[i - 1] > ans) {
          ans = curMax[i - 1];
        }
      }
    }
    return ans;
  }
};
#endif // LEETCODE_42_H
